package com.it.data_tree.tree.leetCodeTopic.tree;


import java.util.LinkedList;

/**
 * @Author: Coke
 * @DateTime: 2023/04/24/21:14
 * @注释: 对TreeNode节点增删查 操作
 **/
public class AddAndDeleteTreeNode {
    TreeNode root;
    /**
     * @Author: CaoYouGen
     * @注释: 求范围和
     * @DateTime: 2023/4/26 15:40
     * @param root: 求哪个根节点中的范围和
     * @param min: 最小节点
     * @param max:  最大节点
     * @return Integer 累加后的和
     */
    Integer sum = 0;
    
    /**
     * @param val: 新增节点的值
     * @作者: Coke
     * @注释: 新增节点
     * @DateTime: 2023/4/24 21:25
     */
    public void putTreeNode (int val) {
        TreeNode node = root;
        TreeNode parent = null;
        while (node != null) {
            parent = node;
            // 传入的值比当前值小
            if (val < node.val) {
                node = node.left;
                // 传入的值比当前大
            } else if (val > node.val) {
                node = node.right;
                // 传入的值等于当前值
            } else {
                node.val = val;
                break;
            }
        }
        // 如果node为空
        if (parent == null) {
            root = new TreeNode(val);
            // 向左新增节点
        } else if (val < parent.val) {
            parent.left = new TreeNode(val);
            // 向右新增节点
        } else if (val > parent.val) {
            parent.right = new TreeNode(val);
        }
    }
    
    /**
     * @param val: 需要查询的值
     * @return TreeNode 返回值对应的节点
     * @Author: CaoYouGen
     * @注释: 查询二叉树节点
     * @DateTime: 2023/4/25 16:20
     */
    public TreeNode getTreeNode (int val) {
        TreeNode node = root;
        if (node == null) {
            // 树不存在
            return null;
        }
        while (node != null) {
            // 向左找
            if (val < node.val) {
                // 向右找
                node = node.left;
            } else if (val > node.val) {
                node = node.right;
                // 情况一：找到了
            } else {
                return node;
            }
        }
        // 情况二：没有查找到(节点不存在)
        return null;
    }
    
    /**
     * @param val: 需要删除的节点
     * @return TreeNode  返回删除的节点
     * @作者: Coke
     * @注释: 删除TreeNode节点
     * @DateTime: 2023/4/25 20:54
     */
    public TreeNode deleteTreeNode (int val) {
        TreeNode node = root;
        TreeNode parent = null;
        
        while (node != null) {
            // 情况一：没有找到
            if (val < node.val) {
                parent = node;
                node = node.left;
            } else if (val > node.val) {
                parent = node;
                node = node.right;
                // 情况二：找到了
            } else {
                break;
            }
        }
        
        if (parent == null && node.val != val) {
            return null;
        }
        
        // 1. 删除的元素为叶子节点
        if (node.right == null && node.left == null) {
            shift(parent, node, null);
            // 2. 删除的元素只有左子节点
        } else if (node.right == null) {
            shift(parent, node, node.left);
            // 3. 删除的元素只有右子节点
        } else if (node.left == null) {
            shift(parent, node, node.right);
            // 4. 删除的元素既有左子节点又有右子节点 (找后继节点 右节点中最小的元素)
        } else {
            TreeNode rightMinNode = node.right;
            TreeNode rParent = node;
            while (rightMinNode.left != null) {
                rParent = rightMinNode;
                rightMinNode = rightMinNode.left;
            }
            
            // 删除的节点与后继节点不相邻， 处理后继节点的后事（只有右节点）
            if (node != rParent) {
                shift(rParent, rightMinNode, rightMinNode.right);
                rightMinNode.right = node.right;
            }
            shift(parent, node, rightMinNode);
            rightMinNode.left = node.left;
        }
        return node;
    }
    
    /**
     * @param parent:   删除节点的父节点
     * @param node:     删除的当前节点
     * @param children: 删除节点的子节点
     * @Author: CaoYouGen
     * @注释: 执行删除节点功能（仅限于删除节点只有左节点或者只有右节点）
     * @DateTime: 2023/4/26 8:35
     */
    public void shift (TreeNode parent, TreeNode node, TreeNode children) {
        // 父节点为空
        if (parent == null) {
            root = children;
        } else if (parent.left == node) {
            parent.left = children;
        } else {
            parent.right = children;
        }
    }
    
    /**
     * @param root: 需要判断的二叉树
     * @return Boolean  是否合法
     * @Author: CaoYouGen
     * @注释: 判断二叉树是否合法 （使用中序遍历 -- 非递归）
     * @DateTime: 2023/4/26 12:45
     */
    
    public boolean isNotLegal (TreeNode root) {
        // 当前节点
        TreeNode node = root;
        // stack栈用于存储 经过的节点
        LinkedList<TreeNode> stack = new LinkedList<>();
        // 用于存储上一个节点的值
        long min = Long.MIN_VALUE;
        
        while (node != null || ! stack.isEmpty()) {
            // 节点不为空 继续往左找
            if (node != null) {
                stack.push(node);
                node = node.left;
                // 已经没有左节点 弹栈 处理值
            } else {
                TreeNode pop = stack.pop();
                // 如果上一个节点的值 大于等于当前节点 说明不合法
                if (min >= pop.val) {
                    return false;
                }
                // 当前节点的值赋值给上一个节点
                min = pop.val;
                // 继续向右找
                node = pop.right;
            }
        }
        return true;
    }
    
    /**
     * @param node: 需要判断的二叉树
     * @return Boolean  是否合法
     * @Author: CaoYouGen
     * @注释: 判断二叉树是否合法 （使用中序遍历 -- 递归）
     * @DateTime: 2023/4/26 14:36
     */
    public boolean isNotLegal2 (TreeNode node) {
        // 初始化时 最小值和最大值为null
        return helper(node, null, null);
    }
    
    /**
     * @param node: 当前节点
     * @param min:  最小值
     * @param max:  最大值
     * @return boolean
     * @Author: CaoYouGen
     * @注释: 判断二叉树是否合法 （执行逻辑）
     * @DateTime: 2023/4/26 14:43
     */
    
    private boolean helper (TreeNode node, Integer min, Integer max) {
        // 如果节点为空 返回true
        if (node == null) {
            return true;
        }
        
        // 如果当前节点的值小于最小值 或者大于最大值 返回false
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        
        // 递归左子树 最小值为当前节点的最小值 最大值为当前节点的值
        if (! helper(node.left, min, node.val)) {
            return false;
        }
        
        // 递归右子树 最小值为当前节点的值 最大值为当前节点的最大值
        if (! helper(node.right, node.val, max)) {
            return false;
        }
        
        // 如果左子树和右子树都合法 则该二叉树合法
        return true;
    }

    /**
     * @Author: CaoYouGen
     * @注释: 求范围和
     * @DateTime: 2023/4/27 10:51
     *
     * @param node:
     * @param min: 最小边界
     * @param max: 最大边界
     * @return Integer 范围和
     */
    public Integer sum (TreeNode node, Integer min, Integer max) {
        // 用于记录二叉树范围和的变量
        if (node == null) {
            return 0;
        }
        // 右边递归
        if (node.val < min) {
            sum(node.right, min, max);
            // 左边递归
        } else if (node.val > max) {
            sum(node.left, min, max);
            // 左右两边都要递归
        } else {
            // 将节点的值加到sum中
            sum += node.val;
            sum(node.left, min, max);
            sum(node.right, min, max);
        }
        // 返回范围和
        return sum;
    }


    /**
     * @Author: CaoYouGen
     * @注释: 根据前序遍历结果建树
     * @DateTime: 2023/4/27 11:29
     *
     * @param preorder: 前序遍历的数组
     * @return TreeNode 构建后的树
     */

    public TreeNode buildTreeByPreorder(Integer[] preorder){
        // 如果序列为空直接返回null
        if (preorder == null || preorder.length == 0){
            return null;
        }
        // 调用辅助函数进行递归调用
        return buildTreeHelper(preorder, 0, preorder.length - 1);
    }
        /**
         * @Author: CaoYouGen
         * @注释: TODO
         * @DateTime: 2023/4/27 12:34
         *
         * @param preorder:
         * @param start: 起始位置
         * @param end: 结束位置
         * @return TreeNode
         */
    // [4, 2, 1, 3, 5, 6, 8, 7, 9]
    private TreeNode buildTreeHelper(Integer[] preorder, Integer start, Integer end){
        // 如果起始位置大于结束位置 直接返回null
        if (start > end){
            return null;
        }

        TreeNode node = new TreeNode(preorder[start]);
        Integer i;
        // 找到左子树和右子树的分界点
        for (i = start + 1; i <= end; i++) {
            // start + 1 ~ i - 1 之间为左子树
            // i ~ end 之间为右子树
            if (preorder[i] > node.val){
                break;
            }
        }

        // 递归构建左子树 和 右子树
        node.left = buildTreeHelper(preorder,start + 1,i -1);
        node.right = buildTreeHelper(preorder, i, end);
        // 返回根节点
        return node;
    }

    /**
     * @Author: CaoYouGen
     * @注释: 二叉树中 求两个节点的最近公共祖先
     * @DateTime: 2023/4/27 14:14
     *
     * @param root: 树 -- 根节点
     * @param p:  节点1
     * @param q:  节点2
     * @return TreeNode 最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        // 如果根节点为空 返回null
        if (root == null){
            return null;
        }
        // 如果p 和 q 的值都小于根节点的值，递归左子树
        if (p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        // 如果p 和 q的值都大于根节点的值，递归右子树
        if (p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        // 如果p 和 q的值在根节点的两侧，那么根节点就是他们最近的公共祖先
        return root;
    }
}
